package com.xiaofu.sort.count;

import com.xiaofu.sort.Sort;

/**
 * @author: xiaofu
 * @DESCRIPTION: a technology seeker
 * @date: 2021-08-10 23:42
 */
public class CountingSort extends Sort {
    @Override
    protected void sort() {
        //找出最大值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
            if (array[i] < min){
                min = array[i];
            }
        }

        //开辟内存空间,存储每个整数出现的次数
        int[] counts = new int[max-min + 1];
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }
        //累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        //从后往前遍历元素,将它放到有序数组中合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length -1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = newArray[i];
        }
    }

    protected void sort0(){
        //找出最大值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
            if (array[i] < min){
                min = array[i];
            }
        }

        //开辟内存空间,存储每个整数出现的次数
        int[] counts = new int[1+max];
        for (int i = 0; i < array.length; i++) {
            counts[array[i]]++;
        }

        //根据整数的出现次数,对整数进行排序
        int index = 0;
        for (int i = min; i < counts.length; i++) {
            while (counts[i]-- >0){
                array[index++] = i;
            }
        }
    }
}
